package com.muchfish.algorithm.array;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * <a href="https://leetcode.cn/problems/3sum/description/">题目：15. 三数之和</a>
 * <br>
 * 题目描述：<br>
 * 给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，<br>
 * 同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。<br>
 * 解题思路：<br>
 * 1.方法一：排序 + 双指针{@link #threeSum1}<br>
 * 1.1 排序，将数组从小到大排序<br>
 * 1.2 枚举从头开始往后枚举，定义枚举变量为a,后续两个指针为b和c，符合要求的数据就是满足a+b+c=0,或者b+c=-a<br>
 * 1.3 定于两指针b和c,b初始从a后一位置开始遍历，指针向数组末尾移动，即b++，c指针从数组末尾即n-1位置开始，不断向数组开始位置移动，即c--<br>
 * 1.4 b,c指针移动结束的临界条件为 b==c(索引相等)，期间找到符合a+b+c=0的数<br>
 * 1.5 上述一轮完成后，a再往后遍历一个数，继续上一轮的b,c指针移动。直到a遍历完所有的数，即找到了所有的满足三数之后的数<br>
 * 细节1：因题干要求给出不重复的三元组，所以计算过程中需要去重。<br>
 *  细节1.1 a需要去重，已经算过了a不能再算，因为是有序数组，所以只需要判断是否和上一个数相同即可，相同就跳过计算，即去重了<br>
 *  细节1.2 b需要去重，在a确定下的b再去重，同样只用和a确定下的上一个b比较即可<br>
 *  细节1.3 c需要去重，本解法的做法是当b+c > -a时，c不断的向前移，其中略过了c部分重合的数据，而b+c = -a时，获得结果后，直接开始计算了下一轮b，也排除了符合解题结果时的去重，这两点，完成了c的所有去重<br>
 * 2. 方法二 排序 + 双指针{@link #threeSum}<br>
 * 2.1 首先对数组进行排序，排序后固定一个数 nums[i]<br>
 * 2.2 再使用左右指针指向 nums[i]后面的两端，数字分别为 nums[L] 和 nums[R]，计算三个数的和 sum 判断是否满足为 0，满足则添加进结果集<br>
 * 2.3 如果 nums[i]大于 0，则三数之和必然无法等于 0，结束循环<br>
 * 2.4 如果 nums[i] == nums[i−1]，则说明该数字重复，会导致结果重复，所以应该跳过<br>
 * 2.5 当 sum == 0 时，nums[L] == nums[L+1] 则会导致结果重复，应该跳过，L++<br>
 * 2.6 当 sum == 0 时，nums[R] == nums[R−1] 则会导致结果重复，应该跳过，R−−<br>
 *<img src="https://pic.leetcode-cn.com/05bd0c05ada0193c35575e91a2dcb47496b2f970bcee0b60c5610bb3b0e1d5ee-0.png"><br>
 */
public class Array9 {
    public static void main(String[] args) {
        int[] nums = new int[]{-1,0,1,1,1,1,2,-1,-4};
        List<List<Integer>> lists = threeSum(nums);
        System.out.println("lists = " + lists);
    }

    private static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ans = new ArrayList();
        int len = nums.length;
        if(nums == null || len < 3) return ans;
        Arrays.sort(nums); // 排序
        for (int i = 0; i < len ; i++) {
            if(nums[i] > 0) break; // 如果当前数字大于0，则三数之和一定大于0，所以结束循环
            if(i > 0 && nums[i] == nums[i-1]) continue; // 去重
            int L = i+1;
            int R = len-1;
            while(L < R){
                int sum = nums[i] + nums[L] + nums[R];
                if(sum == 0){
                    ans.add(Arrays.asList(nums[i],nums[L],nums[R]));
                    while (L<R && nums[L] == nums[L+1]) L++; // 去重
                    while (L<R && nums[R] == nums[R-1]) R--; // 去重
                    L++;
                    R--;
                }
                else if (sum < 0) L++;
                else if (sum > 0) R--;
            }
        }
        return ans;
    }

    public static List<List<Integer>> threeSum1(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        // 枚举 a
        for (int first = 0; first < n; ++first) {
            // 需要和上一次枚举的数不相同
            if (first > 0 && nums[first] == nums[first - 1]) {
                continue;
            }
            // c 对应的指针初始指向数组的最右端
            int third = n - 1;
            int target = -nums[first];
            // 枚举 b
            for (int second = first + 1; second < n; ++second) {
                // 需要和上一次枚举的数不相同
                if (second > first + 1 && nums[second] == nums[second - 1]) {
                    continue;
                }
                // 需要保证 b 的指针在 c 的指针的左侧
                while (second < third && nums[second] + nums[third] > target) {
                    --third;
                }
                // 如果指针重合，随着 b 后续的增加
                // 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环
                if (second == third) {
                    break;
                }
                if (nums[second] + nums[third] == target) {
                    List<Integer> list = new ArrayList<Integer>();
                    list.add(nums[first]);
                    list.add(nums[second]);
                    list.add(nums[third]);
                    ans.add(list);
                }
            }
        }
        return ans;
    }

}
